'''JAVA
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    res += 1;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    void dfs(char[][] grid, int r, int c){
        int row = grid.length;
        int col = grid[0].length;
        if (r<0 || c <0 || r >= row || c >= col || grid[r][c] == '0'){
            return;
        }
        grid[r][c] = '0';

        dfs(grid,r-1, c);
        dfs(grid,r+1, c);
        dfs(grid, r,c-1);
        dfs(grid, r,c+1);
    }
}
'''


class Solution:
    def numIslands(self, grid) -> int:
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    res += 1
                    self.dfs(grid, i, j)
        return res

    def dfs(self, grid, r, c):
        row = len(grid)
        col = len(grid[0])

        if r < 0 or c < 0 or r >= row or c >= col or grid[r][c] == '0':
            return

        grid[r][c] = '0'

        self.dfs(grid, r - 1, c)
        self.dfs(grid, r + 1, c)
        self.dfs(grid, r, c + 1)
        self.dfs(grid, r, c - 1)